class Solution {
public:
    int numberOf2sInRange(int n) 
    {
        //数位dp可以使用一个固定的模板套路来解决，完成一个函数dfs(i,cnt,islimit),这个函数的目的就是
        //从数字i开始往后进行构造数字2出现的次数为cnt次，islimit代表着当前当一次的选择是否受到上一次选择的约束
        //使用数位DP的方法解决
        //首先将n转化为字符串
        auto s = to_string(n);
        int m = s.length();
        vector<vector<int>> dp(m,vector<int>(m,-1));
        function<int(int,int,bool)> g = [&](int i,int cnt,bool islimit)->int
        {
            if(i == m)
            {
                //已经填写完毕了
                return cnt;
            }
            if(!islimit&&dp[i][cnt]>=0)
            {
                return dp[i][cnt];
            }
            int res = 0;
            for (int d = 0, up = islimit ? s[i] - '0' : 9; d <= up; ++d) // 枚举要填入的数字 d
            //如果这个位置的值受到限制，那么这个位置只能选择从0到s[i]这个位置的值，选择了其它的值就会出现大于n的情况
            //如果这个位置的值没有受到约束，那么这个位置的值就可以选择从0到，因为这道题目只是询问2出现的次数
            //所以前导0并不会影响答案，所以不需要处理前导0
                res += g(i + 1, cnt + (d == 2), islimit && d == up);
            if (!islimit) dp[i][cnt] = res;
            return res;
        };//这个函数的目的就是判断从字符0构造到字符n的过程中字符2出现的次数为cnt次，islimit代表我现在填写的这一位是否
        //受到前面填写数字的影响
        int ret = g(0,0,true);
        return ret;    
    }
};